package main

import (
	"fmt"
	"sort"
)

// nums 分为k个子集，子集和相等

func canPartitionKSubsets(nums []int, k int) bool {
	totalSum := 0 
	for _,v := range nums{
		totalSum+=v
	}
	if totalSum%k!=0 {
		return false
	}
	sort.Ints(nums)

	target := totalSum/k   
	n := len(nums)
	// 搜索nums，求k个组合
	var dfs func(idx,curSum int,meetCnt int, vis []bool) bool
	dfs = func(idx, curSum int,meetCnt int,vis []bool) bool{
		if meetCnt == k {
			return true
		}
		if curSum == target {
			return dfs(n-1, 0, meetCnt+1, vis)
		}

		for i:=idx;i>=0;i--{  // 从后往前，顺序
			if vis[i] || curSum + nums[i] > target {
				continue
			}
			vis[i] = true
			if dfs(i-1,curSum+nums[i],meetCnt,vis) {
				return true
			}
			vis[i] = false  // 回溯
			if curSum == 0 {
				return false
			}
		}	
		return false
	}
	vis := make([]bool,n)
	return dfs(n-1,0,0,vis)
}

func main() {
	nums := []int{4,3,2,3,5,2,1}
	k:=1
	res := canPartitionKSubsets(nums,k)
	fmt.Println(res)
}